import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description :
 * User: jiume
 * Date: 2024-09-16
 * Time: 16:08
 */
class Solution {
    // 双层双指针会忽略一些数据
    /*public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        int i = 0;
        int j = nums.length-1;
        while (i < j) {
            List<Integer> sub_list = new ArrayList<>();
            // 注意left和right的取值
            int left = i+1;
            int right = j-1;
            while (left < right) {
                // 注意：对于内层循环来说，只有left和right是可变化的，i、j都是固定的
                if (nums[i]+nums[j]+nums[left]+nums[right] == target) {
                    sub_list.add(nums[i]);
                    sub_list.add(nums[j]);
                    sub_list.add(nums[left]);
                    sub_list.add(nums[right]);
                    List<Integer> integerList = new ArrayList<>(sub_list);
                    list.add(integerList);
                    sub_list.clear();
                    left++;
                    right--;
                    while(left < right && nums[right] == nums[right+1]) {
                        right--;
                    }
                    while(left < right && nums[left] == nums[left-1]) {
                        left++;
                    }
                } else if (nums[i]+nums[j]+nums[left]+nums[right] > target) {
                    right--;
                    while(left < right && nums[right] == nums[right+1]) {
                        right--;
                    }
                } else {
                    left++;
                    while(left < right && nums[left] == nums[left-1]) {
                        left++;
                    }
                }
            }
            i++;
            j--;
            while (i < j && nums[i] == nums[i-1]) {
                i++;
            }
            while (i < j && nums[j] == nums[j+1]) {
                j--;
            }
        }
        return list;
    }*/


    // 正确解法：双层for循环+对撞指针+查找数据时去重
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList<>();
        // 1、排序
        Arrays.sort(nums);
        // 2、开始找数据+去重操作
        for (int i = 0; i <= nums.length - 4; ) {
            for (int j = i + 1; j <= nums.length - 3; ) {
                List<Integer> sub_list = new ArrayList<>();
                int left = j + 1;
                int right = nums.length - 1;
                while (left < right) {
                    if (((long) nums[i] + nums[j] +
                            nums[left] + nums[right]) == target) {
                        sub_list.add(nums[i]);
                        sub_list.add(nums[j]);
                        sub_list.add(nums[left]);
                        sub_list.add(nums[right]);
                        List<Integer> integerList = new ArrayList<>(sub_list);
                        list.add(integerList);
                        sub_list.clear();
                        left++;
                        right--;
                        while (left < right && nums[right] == nums[right + 1]) {
                            right--;
                        }
                        while (left < right && nums[left] == nums[left - 1]) {
                            left++;
                        }
                    } else if ((long) nums[i] + nums[j] +
                            nums[left] + nums[right] > target) {
                        right--;
                        while (left < right && nums[right] == nums[right + 1]) {
                            right--;
                        }
                    } else {
                        left++;
                        while (left < right && nums[left] == nums[left - 1]) {
                            left++;
                        }
                    }
                }
                j++;
                while (j <= nums.length - 3 && nums[j] == nums[j - 1]) {
                    j++;
                }
            }
            i++;
            while (i >= 1 && i <= nums.length - 4 && nums[i] == nums[i - 1]) {
                i++;
            }
        }
        return list;
    }


    public static void main(String[] args) {
        int[] nums = {-3,-1,0,2,4,5};
        fourSum(nums, 0);
    }
}